package binary;

/**
 * 找出第一个小于目标元素的索引
 * https://mp.weixin.qq.com/s/1ExIav9uK4bvVnnf4t0H2Q
 *
 * @auther yang
 * @date 2022/3/18 10:55
 */
public class SearchLessThanTarget {

    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 5, 6, 6, 8, 9, 11};
        int target = 12;
        System.out.println(search(nums, target));
    }

    private static int search(int[] a, int target) {
        int lo = 0, hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + ((hi - lo) >> 1);
            if (a[mid] < target) {
                if (mid == a.length - 1 || a[mid + 1] >= target) {
                    return mid;
                }
                lo = mid + 1;
            } else if (a[mid] >= target) {
                hi = mid - 1;
            }
        }
        return -1;
    }

}

